package Hot100;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author zhangmin
 * @create 2022-01-10 16:16
 */
public class decodeString394 {
    /**
     * 394. 字符串解码
     * 给定一个经过编码的字符串，返回它解码后的字符串。
     * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
     * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
     * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
     * 栈:当遇到数字时，组合成数字入栈，当遇到[和字符时直接入栈，当遇到]时，开始出栈，直到[出栈的反顺序是需要重复的字符串，
     * 然后取出栈顶的数字。
     * */
    int ptr;
    public String decodeString(String s) {
        LinkedList<String> stack=new LinkedList<>();
        ptr=0;
        while (ptr<s.length()){
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)){
                StringBuffer sb=new StringBuffer();
                while (Character.isDigit(s.charAt(ptr))){
                    sb.append(s.charAt(ptr++));
                }
                stack.addLast(sb.toString());
            }else if (Character.isLetter(cur)||cur=='['){
                stack.addLast(String.valueOf(s.charAt(ptr++)));
            }else {
                ++ptr;
                LinkedList<String> list=new LinkedList<>();
                while (!("[").equals(stack.peekLast())){
                    //出栈组成需要重复的元素
                    list.addLast(stack.removeLast());
                }
                //翻转的顺序才是字符串的顺序
                Collections.reverse(list);
                String str=getString(list);
                //左括号出栈
                stack.removeLast();
                int times = Integer.parseInt(stack.removeLast());
                StringBuffer sb=new StringBuffer();
                while (times-->0){
                    sb.append(str);
                }
                stack.add(sb.toString());
            }
        }
        return getString(stack);
    }
    String getString(LinkedList<String> list){
        StringBuffer sb=new StringBuffer();
        for (String s:list) {
            sb.append(s);
        }
        return sb.toString();
    }
}
